package chapter04_RecursionAndDynamic;

import jdk.nashorn.internal.ir.ReturnNode;

/**
 * 描述：排成一条线的纸牌博问题
 *      给定一个整型数组arr,代表数值不同的纸牌排成一条线。 玩家A和玩家B依次拿走
 *      每张纸牌，规定玩家A先拿,玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌，
 *      玩家A和玩家B都绝项聪明。请返回最后获胜者的分数。
 * @author hl
 * @date 2021/7/24 10:16
 */
public class CardGame {
    public static void main(String[] args) {
        int[] arr = {1,2,100,4};
        CardGame cardGame = new CardGame();
        int win = cardGame.win1(arr);
        int win2 = cardGame.win2(arr);
        System.out.println(win);
        System.out.println(win2);
    }

    /**
     * 暴力递归
     * @return
     */
    public int win1(int[] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
    }

    /**
     * 在(l,r)的范围中先手获得的最高分数
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private int f(int[] arr, int l, int r) {
        if (l == r) {
            return arr[l];
        }
        //我方先手，可以以选择arr[l]或者arr[r]，后续可获得的分数为s(arr,l+1,r)何s(arr,l,r-1)，我们选择可获得的最大的分数
        return Math.max(s(arr, l + 1, r) + arr[l], s(arr, l, r - 1) + arr[r]);
    }

    /**
     * 在(l,r)的范围中后手获得的最高分数
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private int s(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        //对方可以选择arr[l]或者arr[r]，我方可以选择的情况有f(arr,l+1,r)和f(arr,l,r-1)，
        //然而选择权在对方手中，对方是绝顶聪明，那么必然会把最差的结果留给我方
        return Math.min(f(arr, l + 1, r), f(arr, l, r - 1));
    }

    /**
     * 动态规划
     * @param arr
     * @return
     */
    public int win2(int[] arr){
        int n = arr.length;
        int[][] f = new int[n][n];
        int[][] s = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = arr[i];
            for (int j = i + 1; j < n; j++) {
                f[i][j] = Math.max(s[i + 1][j] + arr[i], s[i][j - 1] + arr[j]);
                s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
            }
        }
        return Math.max(f[0][n - 1], s[0][n - 1]);
    }
}
